package chapter04_RecursionAndDynamic.feibona;

/**
 * 描述：
 *      假设农场中成熟母牛每年只会生一只小母牛，并且永远都不会死。第一年农场中只有一头母牛，第二年母牛开始生小母牛
 *      小母牛三年后成熟，请问N年后农场中有多少头牛
 * @author hl
 * @date 2021/6/3 11:56
 */
public class CowNum {
    public static void main(String[] args) {
        CowNum cowNum = new CowNum();
        int n = 10;
        System.out.println(cowNum.g1(n));
        System.out.println(cowNum.g2(n));
        System.out.println(cowNum.g3(n));
    }
    public int g1(int n){
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        return g1(n - 1) + g1(n - 3);
    }

    public int g2(int n){
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        int n1 = 3, n2 = 2, n3 = 1, temp = 0;
        for (int i = 4; i <= n; i++) {
            temp = n3;
            n3 = n2;
            n2 = n1;
            n1 += temp;
        }
        return n1;
    }

    /**
     * 这是一个三阶递推数列，可以用3*3的矩阵形式表示，base矩阵
     *      (Cn, C(n-1), C(n - 2)) = (C(n-1), C(n-2), C(n-3)) * [[1,1,0],[0,0,1],[1,0,0]]
     * @param n
     * @return
     */
    public int g3(int n){
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        int[][] base = {{1,1,0},{0,0,1},{1,0,0}};
        int[][] res = MatrixPower.matrixPower(base, n - 3);
        return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
    }
}
